package problem64_MinimumPathSum;

public class MySolution {
	public int minPathSum(int[][] grid) {
		int m=grid.length,n=grid[0].length;
		int[][] minPathGrid=new int[m][n];
		int j=n-1;
		while(j>=0){
			for(int i=m-1;i>=0;i--){
				if(i==m-1&&j==n-1){
					minPathGrid[i][j]=grid[i][j];
				}else{
					int minPath=Math.min(i+1<m?minPathGrid[i+1][j]:Integer.MAX_VALUE,j+1<n?minPathGrid[i][j+1]:Integer.MAX_VALUE);
					minPathGrid[i][j]=grid[i][j]+minPath;
				}
			}
			j--;
		}
		return minPathGrid[0][0];
    }
	
	public static void main(String[] args){
		System.out.println(new MySolution().minPathSum(new int[][]{{0,1,7},{2,3,4},{2,5,6}}));
		System.out.println(new MySolution().minPathSum(new int[][]{{1}}));
	}
}
